#include <iostream>

using namespace std;
// 155. 最小栈
// 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
// 实现 MinStack 类:
// MinStack() 初始化堆栈对象。
// void push(int val) 将元素val推入堆栈。
// void pop() 删除堆栈顶部的元素。
// int top() 获取堆栈顶部的元素。
// int getMin() 获取堆栈中的最小元素。
class MinStack {
public:
    MinStack() {
        obj = new SNode();  // 创建链栈的头结点
    }
    // 销毁栈
    ~MinStack() {
        auto *pre = obj, *p = obj->next;    // pre指向头结点，p指向首结点
        while(p != nullptr) {   // 循环到p为空
            delete pre;
            pre = p;
            p = p->next;
        }
        delete pre;
    }
    // 元素x进栈
    void push(int val) {
        auto *p = new SNode();
        p->data = val;  // 创建结点p存放x
        if(obj->next == nullptr || obj->next->mindata >= val)   // 栈空或者 val <= 栈顶元素
            p->mindata = val;
        else
            p->mindata = obj->next->mindata;  // 其他情况
        // 将结点p插入到表头
        p->next = obj->next;
        obj->next = p;
    }
    // 出栈
    void pop() {
        auto *p = obj->next;    // p指向首节点
        obj->next = p->next;    //虚拟头结点指向下一个结点为新的首节点
        delete p;
    }
    // 取栈顶元素
    int top() {
        return obj->next->data; // 返回首结点值
    }
    // 取最小元素
    int getMin() {
        return obj->next->mindata;
    }

private:
    struct SNode {
        int data;
        int mindata;
        struct SNode *next;
        SNode(): data(0), mindata(INT_MAX), next(nullptr){}
    };
    SNode* obj; // 虚拟头结点
};

int main() {
    auto *minStack = new MinStack();
    minStack->push(-2);
    minStack->push(0);
    minStack->push(-3);
    cout << minStack->getMin() << endl; // 返回-3
    minStack->pop();
    cout << minStack->top() << endl;    // 返回0
    cout << minStack->getMin() <<endl;  // 返回-2
    return 0;
}
